package com.alexd.leetcode.contest.week102;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeSet;

public class Solution3_AC {
	public int sumSubarrayMins(int[] a) {
        long ans = 0;
        LinkedList<Integer> nextMax = new LinkedList<>();
        int [] right = new int [a.length];
        for(int s = a.length - 1 ; s >= 0 ; s--) {
            while(nextMax.size() > 0 && a[nextMax.getLast()] >= a[s]) {
                nextMax.removeLast();
            }
            right[s] = (nextMax.size() == 0 ? a.length : nextMax.getLast()) - s;
            nextMax.add(s); 
        }
        nextMax.clear();
        
        for(int s = 0 ; s < a.length ; s++) {
            while(nextMax.size() > 0 && a[nextMax.getLast()] > a[s]) {
                nextMax.removeLast();
            }
            int leftLength = s - (nextMax.size() == 0 ? -1 : nextMax.getLast()) ;
            ans += (leftLength * right[s] * a[s]) % 1_000_000_007;
            ans %= 1_000_000_007;
            nextMax.add(s);    
        }
        
        return (int)ans;
    }
	public int sumSubarrayMins2(int[] A) {
        ArrayList<ArrayList<Integer>> pos = new ArrayList<ArrayList<Integer>>();
        TreeSet<Integer> ins = new TreeSet<Integer>();
        ins.add(-1);
        ins.add(A.length);
        int ans = 0;
        for (int i = 0; i <= 30000; i++)
            pos.add(new ArrayList<Integer>());
        for (int i = 0; i < A.length; i++) {
            pos.get(A[i]).add(i);
        }
        for (int i = 0; i <= 30000; i++) {
            for (int j : pos.get(i)) {
                int lc = j-ins.floor(j);
                int rc = ins.ceiling(j)-j;
                long mul = lc*rc;
                ins.add(j);
                mul *= i;
                mul %= 1000000007;
                ans += (int)mul;
                ans %= 1000000007;
            }
        }
        return ans;
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
